package com.lsa.letcode.the77.combinations;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
    	List<List<Integer>> combinations = new ArrayList<List<Integer>>();
    	
    	Combination c = new Combination(n, k);
    	do{
    		combinations.add(c.asList());
		}
		while(nextPermutation(c));
    		
        return combinations;
    }
    
    public boolean nextPermutation(Combination c) {
    	if (c.bits.length < 2) {
    		return false;
    	}
    	int i;
    	for (i = c.bits.length - 2; i > -1; --i) {
			if (cmp(c.bits[i], c.bits[i + 1]) < 0){
				break;
			}
		}
    	if (i == - 1){
    		reverse(c);
    		return false;
    	}
    	else {
    		int j = i + 1;
    		int minIdx = j;
    		// find j s.t. num[i] < num[j] and num[j] is min
    		for (;j < c.bits.length; j++) {
    			if (cmp(c.bits[i], c.bits[j]) < 0) {
    				minIdx = j;
    			}
    			else {
    				break;
    			}
			}
    		swap(c, i, minIdx);
			reverse(c, i + 1, c.bits.length - 1);
    	}
    	
    	return true;
    }
    
    void swap(Combination c, int from, int to) {
		boolean t = c.bits[from];
		c.flip(from, c.bits[to]);
		c.flip(to, t);
    }
    
    void reverse(Combination c, int from, int to) {
    	int len = to - from + 1;
    	for (int i = from; i < from + len / 2; i++) {
    		int j = to - (i - from);
    		swap(c, i, j);
		}
    }
    
    void reverse(Combination c) {
    	reverse(c, 0, c.bits.length - 1);
    }
    
    static class Combination {
    	boolean[] bits;
    	
    	Combination(int n, int k) {
    		bits = new boolean[n];
    		for (int i = 0; i < k; i++) {
        		flip(n - i - 1, true);
    		}
    	}
    	
    	List<Integer> asList(){
    		List<Integer> l = new ArrayList<Integer>();
    		
    		for (int i = 0; i < bits.length; i++) {
				if (bits[i]) {
					l.add(i + 1);
				}
			}
    		
    		return l;
    	}
    	
    	void flip(int i, boolean bit) {
    		bits[i] = bit;
    	}
    }
    
    static int cmp(boolean b1, boolean b2) {
    	if (b1) {
    		return b2? 0 : 1;
    	}
    	else{
    		return b2? -1 : 0;
    	}
    }
}